/*************************************************************************
 * File Name:    Best_Time_to_Buy_and_Sell_Stock_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 03 Nov 2013 10:25:50 AM CST
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Best Time to Buy and Sell Stock II
 |
 | Say you have an array for which the ith element is the price of a given stock on day i.
 |
 | Design an algorithm to find the maximum profit. You may complete as many transactions
 | as you like (ie, buy one and sell one share of the stock multiple times).
 | However, you may not engage in multiple transactions at the same time (ie, you must
 | sell the stock before you buy again).
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    
    int maxProfit(vector<int> &prices)
    {
        int ans = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        
        return ans;
    }
    
    int maxProfit1(vector<int> &prices)
    {
        int N = prices.size();
        vector<int> dp(N + 1, 0);
        
        vector<int> s;
        
        s.push_back(0);
        for (int i = 2; i <= N; ++i) {
            dp[i] = dp[i - 1];
            
            while (!s.empty() && prices[s.back()] >= prices[i - 1]) {
                s.pop_back();
            }
            for (size_t j = 0; j < s.size(); ++j) {
                dp[i] = max(dp[i], dp[s[j]] + prices[i - 1] - prices[s[j]]);
            }
            s.push_back(i - 1);
        }
        return dp[N];
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;

    //vector<int> stock(num, num + sizeof(num) / sizeof(num[0]));
    int arr[] = {3,3,5,0,0,3,1,4};
    vector<int> stock(arr, arr + sizeof(arr) / sizeof(arr[0]));

    cout << sol.maxProfit(stock) << endl;

    return 0;
}
